package com.duoduo.剑指Offer;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @program: algorithm
 * @description: 最长不含重复字符的子字符串19
 * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 *
 * @author: chaidl  ！
 * @create: 2022-05-25 00:20
 */
public class 最长不含重复字符的子字符串19 {
	public int lengthOfLongestSubstring(String s) {
		//    首先判断字符串长度如果是1就直接返回
		int length=s.length();
		if (length<=1){
			return length;
		}
		int left=0,right = 0;
		int maxLength=1;
		Map<Character,Integer> window=new HashMap<>();
		//    当右边界出界的时候跳出循环
		while (right<length){
			char tmp=s.charAt(right);
			//拿到有指针字符的索引
			Integer rightIndex = window.getOrDefault(tmp, -1);
			//然后判断，如果是-1表示没重复，不是-1表示重复，left直接调到重复字符的下一个位置
			left=Math.max(left,rightIndex+1);
			maxLength=Math.max(maxLength,right-left+1);
			window.put(s.charAt(right),right);
			right++;
		}
		return maxLength;
	}
	public int lengthOfLongestSubstring2(String s) {
		int length = s.length();
		if (length<=1){
			return length;
		}
		//定义一个窗口
		Set<Character> window=new HashSet<>();
		int left=0,right = 0;
		int max=1;
		while (right < length){
			//如果窗口里面已经有了，就要将之前的删除
			while (window.contains(s.charAt(right))){
				window.remove(s.charAt(left));
				left++;
			}
			max=Math.max((right - left)+1,max);
		//	向窗口里面添加
			window.add(s.charAt(right));
			right++;
		}
		return max;
	}
}
